class Graph {
    edges = 0;
    vertices;
    adj = [];
    marked = [];
    queue = [];
    edgeTo = [];
    constructor(v) {
        this.vertices = v;
        for (let i = 0; i < v; i++) {
            this.adj[i] = [];
        };
        this.initMarkedArray();
    };
    initMarkedArray() {
        this.marked.fill(false, 0, this.vertices.length - 1);
    };
    addEdge(v, w) {
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    };
    showGraph() {
        let returnData = "";
        this.adj.forEach((item, index) => {
            const vertex = index;
            const nextToVertex = item.join("-");
            returnData += vertex + ": " + nextToVertex + "\n";
        });
        return returnData;
    };
    dfs(v) {
        this.marked[v] = true;
        console.log("vertices: " + v);
        this.adj[v].forEach((item) => {
            if (!this.marked[item]) {
                this.dfs(item);
            }
        });
    };
    bfs(v) {
        if (!this.marked[v]) {
            this.marked[v] = true;
            console.log("vertices: " + v);
            this.adj[v].forEach((item) => {
                this.queue.push(item);
                if(!this.marked[item]) {
                    this.edgeTo[item] = v;
                }
            });
            while (this.queue.length > 0) {
                this.bfs(this.queue.shift());
            }
        }
    };
    pathTo(v) {
        const source = 0;
        const path = [];
        for(let i = v; i !== source; i = this.edgeTo[i]) {
            path.push(i);
        }
        path.push(0);
        return path;
    }
}


const graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(2, 4);

console.log(graph.showGraph());
// graph.dfs(0);
graph.bfs(0);
// console.log(graph.pathTo(4));
console.log(graph.edgeTo)